package com.company.JvmDemo;

import java.util.*;

public class Main {
    public static void main(String[] args) {
    int[] arr = {3,2,1,4,8,5,2,6};
        System.out.println(Arrays.toString(arr));
    heap(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void heap(int[] arr) {
        //构建大顶堆
        for(int i = (arr.length - 1) / 2; i >= 0; i--) {
            sort(arr, i, arr.length);
        }
        for(int x = arr.length - 1;x > 0; x--) {
            int temp=arr[x];
            arr[x]=arr[0];
            arr[0]=temp;
            sort(arr, 0, x);
        }
    }

    public static void sort(int[] arr,int parent,int length) {
        int temp=arr[parent];
        int left=2 * parent + 1;
        while(left < length) {
            int right = left + 1;
            if(right < length && arr[left] < arr[right]) {
                left++;
            }
            if (temp >= arr[left]) {
                break;
            }
            arr[parent] = arr[left];
            parent=left;
            left=2 * left + 1;
        }
        arr[parent]=temp;
    }
}
